package com.structure.algorithm;

/**
 * 二叉树的相关操作
 * 判断一个大的二叉树中是否包含另一个小的二叉树
 * Created by 乔磊 on 2015/10/27.
 */
public class TreeOneHasTreeTwo {
    public boolean isSubtree(TreeNode T1, TreeNode T2) {
        boolean result = false;
        //如果树1和树2都为空，返回存在子树
        if(T1==null && T2==null){
            return true;
        }
        //如果单向父树为空，则返回错误
        if(T1==null){
            return false;
        }
        //如果子树为空，则返回正确，空树是任何非空树的子树
        if(T2==null){
            return true;
        }
        //首先判断根节点是否相等，然后判断父树是否包含子树
        if(T1.val==T2.val){
            result = doesTreeOneHasTreeTwo(T1,T2);
        }
        //根节点判断完成后，开始判断左、右子树
        if(!result){
            result = isSubtree(T1.left,T2);
        }
        if(!result){
            result = isSubtree(T1.right,T2);
        }
        return result;
    }


    public boolean doesTreeOneHasTreeTwo(TreeNode treeOne,TreeNode treeTwo){
        //两个树都为空
        if(treeOne == null && treeTwo == null){
            return true;
        }
        //父树不为空，但是子树为空，返回错误
        if(treeOne!=null && treeTwo ==null){
            return false;
        }
        //同上
        if(treeOne ==null && treeTwo !=null){
            return false;
        }
        //root的节点的值不相等返回错误
        if(treeOne.val !=treeTwo.val){
            return false;
        }
        //左右分别循环
        return doesTreeOneHasTreeTwo(treeOne.left,treeTwo.left)&&doesTreeOneHasTreeTwo(treeOne.right,treeTwo.right);
    }
}

class BinaryTreeNode {
    int nValue;
    BinaryTreeNode rightNode;
    BinaryTreeNode leftNode;
}
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
}

